package other;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/19  10:01
 * @Description:
 */
public class MinString {
    public static void main(String[] args) {
        String s= "22522";
        System.out.println(getMin2(s));
    }
    public static String getMin(String s){
        int i=0, j=1, k=0, len = s.length(), t;
        while(i < len && j < len && k < len) {
            t = s.charAt((i+k)%len) - s.charAt((j+k)%len);
            if(t==0) k++;
            else {
                if(t>0){
                    i = Math.max(i+k+1, j);
                    j = i + 1;
                }
                else j= j + k +1;
                k = 0;
            }
        }
        return s.substring(i) + s.substring(0, i == 0 ? 0 : i);
    }
    public static String getMin2(String s) {
        int i=0, j=1, k=0, len = s.length(), t;
        //表示从i开始k长度和从j开始k长度的字符串相同
        while(i < len && j < len && k < len) {
            t = s.charAt((i+k)%len) - s.charAt((j+k)%len);
            //t用来计算相对应位置上那个字典序较大
            if(t==0) k++;//字符相等的情况
            else {
                if(t > 0) i += k+1;//i位置大,最大表示法: j += k+1
                else j += k+1;//j位置大,最大表示法: i += k+1
                if(i == j) j++;
                k = 0;
            }
        }
        i = Math.min(i, j);
        return s.substring(i) + s.substring(0, i == 0 ? 0 : i);
    }
}
